#
# @lc app=leetcode.cn id=260 lang=python3
#
# [260] 只出现一次的数字 III
#
# https://leetcode.cn/problems/single-number-iii/description/
#
# algorithms
# Medium (71.38%)
# Likes:    922
# Dislikes: 0
# Total Accepted:    159.5K
# Total Submissions: 223.8K
# Testcase Example:  '[1,2,1,3,2,5]'
#
# 给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
#
# 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
#
#
#
# 示例 1：
#
#
# 输入：nums = [1,2,1,3,2,5]
# 输出：[3,5]
# 解释：[5, 3] 也是有效的答案。
#
#
# 示例 2：
#
#
# 输入：nums = [-1,0]
# 输出：[-1,0]
#
#
# 示例 3：
#
#
# 输入：nums = [0,1]
# 输出：[1,0]
#
#
#
#
# 提示：
#
#
# 2 <= nums.length <= 3 * 10^4
# -2^31 <= nums[i] <= 2^31 - 1
# 除两个只出现一次的整数外，nums 中的其他数字都出现两次
#
#
#

from typing import List


# @lc code=start
class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor_all = 0
        for x in nums:
            xor_all ^= x
        low_bit = xor_all & -xor_all
        ans = [0, 0]
        for x in nums:
            ans[x & low_bit != 0] ^= x
        return ans


# @lc code=end
s = Solution()
nums = [
    43772400,
    1674008457,
    1779561093,
    744132272,
    1674008457,
    448610617,
    1779561093,
    124075538,
    -1034600064,
    49040018,
    612881857,
    390719949,
    -359290212,
    -812493625,
    124732,
    -1361696369,
    49040018,
    -145417756,
    -812493625,
    2078552599,
    1568689850,
    865876872,
    865876872,
    -1471385435,
    1816352571,
    1793963758,
    2078552599,
    -1034600064,
    1475115274,
    -119634980,
    124732,
    661111294,
    -1813882010,
    1568689850,
    448610617,
    1347212898,
    -1293494866,
    612881857,
    661111294,
    -1361696369,
    1816352571,
    -1813882010,
    -359290212,
    1475115274,
    1793963758,
    1347212898,
    43772400,
    -1471385435,
    124075538,
    -1293494866,
    -119634980,
    390719949,
]
res = s.singleNumber(nums)
print(res)
